package jp.aist.gtrc.plus.admission.EDF.simulation;

import java.util.*;
import jp.aist.gtrc.plus.admission.EDF.*;

public class Bug {

   public static final int seed = 1115;
   public static final int TESTNUM = 1;  // number of repeated tests
   public static final double[] LOADS = {1.0};
   public static final int CPUNUM = 4;   // number of cpus
   public static final int MINCPUPERFORMANCE = 1;   // min performance index
   public static final int MAXCPUPERFORMANCE = 10;   // max performance index
   public static final int JOBARRAYNUM = 4;  // number of job array
   public static final int interArrivalTime = 2*60;
   public static final int avgNumOfJobs = 10;
   public static final int varNumOfJobs = 5;
   public static final int avgExeTime = 3*30*60; 
   public static final int varExeTime = 20*60; 
   public static final int avgRelativeDeadline = 24*60*60;
   public static final int varRelativeDeadline = 16*60*60;

   private boolean withAdmissionControl = false;
   private boolean withNonPreemptive = false;
   private TreeSet<Event> eventList;
   private Clock clock;
   private Set<UniformCPU> cpus;
   private JobArrivalEventGenerator jobArrivalEventGenerator;
   private EDFAdmissionUniform admission;

   private Map<Job,JobInfo> jobInfoMap;
   private Map<JobArray,JobArrayInfo> jobArrayInfoMap;
   private Map<CPU,CPUInfo> cpuInfoMap;
   private Collection<Job> acceptedJobs;

   public Bug(Clock clock, Set<UniformCPU> cpus, JobArrivalEventGenerator jobArrivalEventGenerator) {
      this.eventList = new TreeSet<Event>();
      this.clock = clock;
      this.cpus = cpus;
      this.jobArrivalEventGenerator = jobArrivalEventGenerator; 
      this.admission = new EDFAdmissionUniform();
      eventList.add(new Event(clock.getCurrentTime(),Event.INIT));

      this.acceptedJobs = new HashSet<Job>();
      this.jobInfoMap = new HashMap<Job,JobInfo>();
      this.jobArrayInfoMap = new HashMap<JobArray,JobArrayInfo>();
      this.cpuInfoMap = new HashMap<CPU,CPUInfo>();
   }

   public void setAdmissionControl(boolean onoff) {
      this.withAdmissionControl = onoff;
   }

   public void setNonPreemptive(boolean onoff) {
      this.withNonPreemptive = onoff;
   }

   private void manuallyAddJobArrivalEvent() {
      eventList.add(new JobArrivalEvent(2,new JobArray("0",5,2,11)));
      eventList.add(new JobArrivalEvent(3,new JobArray("1",10,2,10)));
      eventList.add(new JobArrivalEvent(15,new JobArray("2",2,2,20)));
   }

   public void run() {

      int totalRequestedCPUTime = 0; 
      for (int i=0; i < JOBARRAYNUM; i++) {
         JobArrivalEvent event = jobArrivalEventGenerator.next();
         eventList.add(event); 
         clock.advanceTime(event.getTimestamp());
         JobArray jobArray = event.getJobArray();
         totalRequestedCPUTime = totalRequestedCPUTime + jobArray.numOfJobs*jobArray.exeTime;
      }
      clock.reset();


//      manuallyAddJobArrivalEvent();

      for (CPU cpu : cpus) {
         CPUInfo cpuInfo = new CPUInfo();
         cpuInfoMap.put(cpu,cpuInfo);
      } 


      int lastTimestamp = 0;
      int lastJobExitTime = 0;

      while (eventList.size() > 0) {
         Event event = eventList.first();
         eventList.remove(event);

         try {
            clock.advanceTime(event.getTimestamp());
         } catch (RuntimeException e) {
            System.out.println(e);
            System.out.println(event);
            throw e;
         }

         for (CPU cpu : cpus) {
            CPUInfo cpuInfo = cpuInfoMap.get(cpu);
            if (cpuInfo.isIdle()) {
               cpu.setAvailableTime(clock.getCurrentTime());
            } else {
               int interval = clock.getCurrentTime() - lastTimestamp;
               cpuInfo.addUsageTime(interval);
            }
         }

         switch(event.getType()) {
             case Event.INIT:
                // do nothing
                break;

             case Event.JOB_ARRIVAL:
                JobArrivalEvent jobArrivalEvent = (JobArrivalEvent) event;
                JobArray jobArray = jobArrivalEvent.getJobArray();
                System.out.println("Job " + jobArray.name + " is arrival:" + jobArrivalEvent);
                Collection<Job> newJobs = expandJobArray(jobArray);
                Collection<Job> testedJobs = new HashSet<Job>(acceptedJobs);
                testedJobs.addAll(newJobs);
                if (withAdmissionControl) {

                   /*
                    *  Create dummy CPUs to prevent current state changes 
                    *  (otherwise admission.test() change lastOccupied).
                    */
                   Collection<UniformCPU> dummyCpus = new ArrayList<UniformCPU>();
                   for (UniformCPU cpu : cpus) {
                      dummyCpus.add(new UniformCPU(cpu));
                   }

                   if (admission.buildSchedule(dummyCpus,testedJobs,jobArray)) {
                      queueJobs(clock.getCurrentTime(),jobArray,newJobs);
                      jobArrayInfoMap.put(jobArray,new JobArrayInfo(clock.getCurrentTime(),newJobs)); 
                      System.out.println("Accept job " + jobArray.name);
                   } else {
                      System.out.println("Reject job " + jobArray.name);
                   }
                } else {
                   queueJobs(clock.getCurrentTime(),jobArray,newJobs);
                   jobArrayInfoMap.put(jobArray,new JobArrayInfo(clock.getCurrentTime(),newJobs)); 
                }
                if (withNonPreemptive) {
                   scheduleByNonPreemptiveEDF();
                } else {
                   scheduleByEDF();
                }
                break;
  
             case Event.JOB_EXIT:
                JobExitEvent jobExitEvent = (JobExitEvent) event;
                Job job = jobExitEvent.getJob();
                JobInfo jobInfo = jobInfoMap.get(job);
                CPU cpu = jobInfo.getExecutingCPU();
                CPUInfo cpuInfo = cpuInfoMap.get(cpu);
                jobInfo.done(clock.getCurrentTime());
                cpuInfo.executeJob(null);
                System.out.println("Job " + job.name + " finished, CPU " + cpu.id + " is free at " + clock.getCurrentTime());
                if (withNonPreemptive) {
                   scheduleByNonPreemptiveEDF();
                } else {
                   scheduleByEDF();
                }
                lastJobExitTime = clock.getCurrentTime();
                break;

             case Event.JOB_DEADLINE:
                JobDeadlineEvent jobDeadlineEvent = (JobDeadlineEvent) event;
                job = jobDeadlineEvent.getJob();
                cancelJob(job);   
                break;

             case Event.TERMINATE:
                System.out.println("Simulation is terminiated by event.");
                System.exit(0); 
                break;

             default: 
                System.err.println("Unknown event " + event.getId() + " at time " + clock.getCurrentTime());
                System.exit(1);
                break; 
         }

         lastTimestamp = clock.getCurrentTime();

      }

      System.out.println("Last job exit timestamp = " + lastJobExitTime);
      
      double totalWeightedAvailableCPUTime = 0.0;
      double totalCPUUtil = 0.0;
      System.out.println("\n--------------- CPU Utilization --------------");
      for (UniformCPU cpu : cpus) {
         CPUInfo cpuInfo = cpuInfoMap.get(cpu);
         double x = cpuInfo.getTotalUsageTime()*cpu.performanceIndex;
         System.out.println("CPU " + cpu.id + " uses " + cpuInfo.getTotalUsageTime() + "*" + cpu.performanceIndex + " = " + x);
         totalCPUUtil = totalCPUUtil + x;
         totalWeightedAvailableCPUTime = totalWeightedAvailableCPUTime + cpu.performanceIndex*lastJobExitTime;  
      }
      System.out.println("totalCPUUtil=" + totalCPUUtil);

      System.out.println("\n--------------- Job Statistics ---------------");
      double totalCompletionTime = 0.0;
      double totalWaitingTime = 0.0;
      int numOfSuccessJobArrays = 0;
      int numOfFailJobArrays = 0;
      double totalWeightedUsefulCPUTime = 0.0;
      double totalWastedCPUTime = 0.0;
      List<JobArray> jobArrays = new ArrayList<JobArray>(jobArrayInfoMap.keySet());
      Collections.sort(jobArrays,new JobArrayComparator()); 
      
      for (JobArray jobArray : jobArrays) {
         JobArrayInfo jobArrayInfo = jobArrayInfoMap.get(jobArray);
         boolean done = true;
         int totalExecutionTime = 0;
         int maxStopTime = 0;
         int minStartTime = Integer.MAX_VALUE;
         for (Job job : jobArrayInfo.getJobs()) {
            JobInfo jobInfo = jobInfoMap.get(job);
            if (jobInfo.isDone()) {
               totalExecutionTime = totalExecutionTime + job.exeTime; 
               if (jobInfo.startTime < minStartTime) {
                  minStartTime = jobInfo.startTime;
               }
               if (maxStopTime < jobInfo.stopTime) {
                  maxStopTime = jobInfo.stopTime;
               }
            } else {
               done = false; 
            }
         }
         if (done) {
            System.out.println("JobArray " + jobArray.name + " completed at " + maxStopTime + " using " + totalExecutionTime);
            numOfSuccessJobArrays = numOfSuccessJobArrays + 1; 
            totalCompletionTime = totalCompletionTime + (maxStopTime - jobArrayInfo.getArrivalTime());
            totalWaitingTime = totalWaitingTime + (minStartTime - jobArrayInfo.getArrivalTime());
            jobArrayInfo.setCompletionTime(maxStopTime);
            totalWeightedUsefulCPUTime = totalWeightedUsefulCPUTime + totalExecutionTime;
         } else {
            System.out.println("JobArray " + jobArray.name + " failed and lost " + totalExecutionTime);
            totalWastedCPUTime = totalWastedCPUTime + totalExecutionTime;
            numOfFailJobArrays = numOfFailJobArrays + 1;
         }
         
      }

      System.out.println("\n------------------ Summary -------------------");
      System.out.println("Number of queued jobs = " + jobArrayInfoMap.size());
      System.out.println("Number of success jobs = " + numOfSuccessJobArrays);
      System.out.println("Number of fail jobs = " + numOfFailJobArrays);
      System.out.println("Total completion time = " + totalCompletionTime);
      System.out.println("Total waiting time = " + totalWaitingTime);
      System.out.println("Total weighted available CPU time = " + totalWeightedAvailableCPUTime);
      System.out.println("Total weighted useful CPU time = " + totalWeightedUsefulCPUTime);
      System.out.println("Total wasted CPU time = " + totalWastedCPUTime);
      System.out.println("Number of requested CPU time  = " + totalRequestedCPUTime);
      System.out.println("Total CPU Performance Index = " + Bug.getTotalCPUPerformanceIndex(cpus));

      System.out.println(jobArrayInfoMap.size() + "," + 
                         numOfSuccessJobArrays + "," + 
                         numOfFailJobArrays + "," +
                         totalCompletionTime + "," +
                         totalWaitingTime + "," +
                         totalWeightedAvailableCPUTime + "," +
                         totalWeightedUsefulCPUTime + "," +
                         totalWastedCPUTime + "," + 
                         Bug.getTotalCPUPerformanceIndex(cpus));
      
      
      if (acceptedJobs.size() > 0) {
         System.out.println("Simulation abnormally terminated with remaining jobs in queue");
         for (Job job : acceptedJobs) 
            System.out.println(job.name);
      } else {
         System.out.println("Simulation normally terminated");
      }

   }

   private int nextJobId = 0;
   private Collection<Job> expandJobArray(JobArray jobArray) {
      HashSet<Job> jobs = new HashSet<Job>();
      int id = nextJobId;
      for (int i=0; i < jobArray.numOfJobs; i++) {
         Job job = new Job(id+i,jobArray.name+"/"+i,jobArray.exeTime,jobArray.deadline);
         jobs.add(job);
         nextJobId = nextJobId + 1;
      }
      return jobs;
   }

   private void queueJobs(int arrivalTime, JobArray jobArray, Collection<Job> jobs) {
      for (Job job : jobs) {
         JobInfo jobInfo = new JobInfo(arrivalTime,jobArray);
         acceptedJobs.add(job);
         jobInfoMap.put(job,jobInfo);
         JobDeadlineEvent jobDeadlineEvent = new JobDeadlineEvent(job.deadline+1,job);
         eventList.add(jobDeadlineEvent);
      }
   }

   private UniformCPU getBestCPU(Job job, Collection<UniformCPU> cpus) {
      UniformCPU bestCPU = null;
      int bestCompletionTime = Integer.MAX_VALUE;

      for (UniformCPU cpu : cpus) {
          int t = cpu.lastOccupied + (int) Math.ceil(job.exeTime/cpu.performanceIndex);
          if (t < bestCompletionTime) {
             bestCompletionTime = t;
             bestCPU = cpu;
          }
      }
      return bestCPU;
   }

   private UniformCPU getBestIdleCPU(Job job) {
      UniformCPU bestCPU = null;
      int bestCompletionTime = Integer.MAX_VALUE;

      for (UniformCPU cpu : cpus) {
          CPUInfo cpuInfo = cpuInfoMap.get(cpu);
          if (!cpuInfo.isIdle()) continue;
          int t = cpu.lastOccupied + (int) Math.ceil(job.exeTime/cpu.performanceIndex);
          if (t < bestCompletionTime) {
             bestCompletionTime = t;
             bestCPU = cpu;
          }
      }
      return bestCPU;
   }

   private void cancelJob(Job job) {
      JobInfo jobInfo = jobInfoMap.get(job);
      if (jobInfo.isWaiting()) {
         if (job.deadline <= clock.getCurrentTime()) {
            System.out.println("Cancel accepted job " + job.name + " due to missed deadline " + job.deadline);
            acceptedJobs.remove(job);
         }
      } else if (jobInfo.isExecuting()) {
         System.out.println("Trying to cancel running job " + job.name + " at " + clock.getCurrentTime());
         System.exit(1);
      }
   }

   private void dispatchJob(Job job, UniformCPU cpu) {
      JobInfo jobInfo = jobInfoMap.get(job);
      jobInfo.executeOn(cpu,clock.getCurrentTime());
      int exitTime = clock.getCurrentTime() + (int) Math.ceil(job.exeTime/cpu.performanceIndex);  
      cpu.setAvailableTime(exitTime); // CPU is occupied
      CPUInfo cpuInfo = cpuInfoMap.get(cpu);
      cpuInfo.executeJob(job);  // dispatch the job on the CPU
      System.out.println("Job " + job.name + " (id=" + job.id + ") dispatched on CPU " + cpu.id + " at " + clock.getCurrentTime());
   }

   private void scheduleByEDF() {
      /*
       *  Create dummy CPUs to prevent current state changes (next loops
       *  change lastOccupied).
       */
      Map<UniformCPU,UniformCPU> dummyCPUMap = new HashMap<UniformCPU,UniformCPU>();
      Collection<UniformCPU> dummyCPUs = new ArrayList<UniformCPU>();
      int numOfIdleCPUs = 0;
      for (UniformCPU cpu : cpus) {
         UniformCPU dummyCPU = new UniformCPU(cpu);
         dummyCPUs.add(dummyCPU);
         dummyCPUMap.put(dummyCPU,cpu);
         CPUInfo cpuInfo = cpuInfoMap.get(cpu);
         if (cpuInfo.isIdle()) {
            numOfIdleCPUs = numOfIdleCPUs + 1;
         }
      }

      List<Job> sortedJobs = new ArrayList<Job>(acceptedJobs);
      Collections.sort(sortedJobs,new DeadlineComparator());
      for (int i = 0; i < sortedJobs.size(); i++) {
         if (numOfIdleCPUs <= 0) break;  // no CPU available
         Job selectedJob = sortedJobs.get(i);  // get a job
         UniformCPU selectedDummyCPU = getBestCPU(selectedJob,dummyCPUs);  // get a CPU
System.out.println("Test Job " + selectedJob.name + " with " + selectedDummyCPU.id);
         int exitTime = selectedDummyCPU.lastOccupied + (int) Math.ceil(selectedJob.exeTime/selectedDummyCPU.performanceIndex);
         if (exitTime > selectedJob.deadline) {
         //System.out.println("Job " + selectedJob.name + " missed deadline because of " + exitTime + " > " + selectedJob.deadline);
            continue;
         }
         UniformCPU selectedRealCPU = dummyCPUMap.get(selectedDummyCPU);
         CPUInfo cpuInfo = cpuInfoMap.get(selectedRealCPU);
         if (!cpuInfo.isIdle()) {
//System.out.println("Job  " + selectedJob.name + " skip " + selectedDummyCPU.id + " for better CPU");
            // this job prefers to wait for the busy but faster CPU 
            // and will be dispatched in the future.
            selectedDummyCPU.lastOccupied = exitTime;
            continue;
         }
         selectedDummyCPU.lastOccupied = exitTime;

         dispatchJob(selectedJob,selectedRealCPU);
System.out.println("CPU " + selectedRealCPU.id + " occupied until " + selectedRealCPU.lastOccupied);
         acceptedJobs.remove(selectedJob);
         JobExitEvent jobExitEvent = new JobExitEvent(exitTime,selectedJob); // set event on job exit 
         eventList.add(jobExitEvent);
         numOfIdleCPUs = numOfIdleCPUs - 1;
      }

   }

   private void scheduleByGreedyEDF() {  // only idle CPU is considered
      List<Job> sortedJobs = new ArrayList<Job>(acceptedJobs);
      Collections.sort(sortedJobs,new DeadlineComparator());
      for (int i = 0; i < sortedJobs.size(); i++) {
         Job selectedJob = sortedJobs.get(i);  // get a job
         UniformCPU selectedCPU = getBestIdleCPU(selectedJob);  // get a CPU
         if (selectedCPU == null) break; // no CPU available

         int exitTime = clock.getCurrentTime() + (int) Math.ceil(selectedJob.exeTime/selectedCPU.performanceIndex);  
         if (exitTime > selectedJob.deadline) {
            // Try this job on a faster CPU if it is free in the future
            continue;  // Thus allow backfilling
         }
         dispatchJob(selectedJob,selectedCPU);
         acceptedJobs.remove(selectedJob);
         JobExitEvent jobExitEvent = new JobExitEvent(exitTime,selectedJob); // set event on job exit 
         eventList.add(jobExitEvent);
      }

   }

   private List<Job> preferredJobs = new ArrayList<Job>();
   private void scheduleByNonPreemptiveEDF() {
      for (int i=0; i < preferredJobs.size(); i++) {
         Job selectedJob = preferredJobs.get(i); 
         UniformCPU selectedCPU = getBestIdleCPU(selectedJob);  // get a CPU
         if (selectedCPU == null) break;  // no CPU available

         int exitTime = clock.getCurrentTime() + (int) Math.ceil(selectedJob.exeTime/selectedCPU.performanceIndex);  
         if (exitTime > selectedJob.deadline) {
            // Try this job on a faster CPU if it is free in the future
            continue;  // Thus allow backfilling
         }
         dispatchJob(selectedJob,selectedCPU);
         acceptedJobs.remove(selectedJob);
         preferredJobs.remove(selectedJob);
         JobExitEvent jobExitEvent = new JobExitEvent(exitTime,selectedJob); // set event on job exit 
         eventList.add(jobExitEvent);
      }
      List<Job> sortedJobs = new ArrayList<Job>(acceptedJobs);
      sortedJobs.removeAll(preferredJobs); 
      Collections.sort(sortedJobs,new DeadlineComparator());
      while (sortedJobs.size() > 0) {
         Job selectedJob = sortedJobs.get(0);  // get the first job
         UniformCPU selectedCPU = getBestIdleCPU(selectedJob);  // get a CPU
         if (selectedCPU == null) break;  // no CPU available

         int exitTime = clock.getCurrentTime() + (int) Math.ceil(selectedJob.exeTime/selectedCPU.performanceIndex);  
         if (exitTime > selectedJob.deadline) {
            // Try this job on a faster CPU if it is free in the future
            sortedJobs.remove(selectedJob);
            continue;  // Thus allow backfilling
         }
         dispatchJob(selectedJob,selectedCPU);
         acceptedJobs.remove(selectedJob);

         // Move all jobs in the same group to preferred jobs
         JobInfo jobInfo = jobInfoMap.get(selectedJob);
         JobArrayInfo jobArrayInfo = jobArrayInfoMap.get(jobInfo.jobArray);
         Collection<Job> movingJobs = new ArrayList<Job>(jobArrayInfo.getJobs());
         sortedJobs.removeAll(movingJobs);
         movingJobs.remove(selectedJob);
         preferredJobs.addAll(movingJobs);

         JobExitEvent jobExitEvent = new JobExitEvent(exitTime,selectedJob); // set event on job exit 
         eventList.add(jobExitEvent);
      }
   }

   private static double getTotalCPUPerformanceIndex(Set<UniformCPU> cpus) {
      double totalCPUPerformance = 0.0;
      for (UniformCPU cpu : cpus) {
         totalCPUPerformance = totalCPUPerformance + cpu.performanceIndex;
      }
      return totalCPUPerformance;
   } 

   public static void main(String[] args) throws Exception {
      Random rnd = new Random(seed);

      for (int loadIdx = 0; loadIdx < LOADS.length; loadIdx++) {

         for (int runIdx = 0; runIdx < TESTNUM; runIdx++) {

             System.out.println("load = " + LOADS[loadIdx] + ", run = " + runIdx);
             Clock clock = new Clock();

             int weightedAvgExeTime = (int) (avgExeTime*LOADS[loadIdx]);

            // simulate jobs
            JobArrivalEventGenerator jobArrivalEventGenerator = new JobArrivalEventGenerator(clock,interArrivalTime,avgNumOfJobs,varNumOfJobs,weightedAvgExeTime,varExeTime,avgRelativeDeadline,varRelativeDeadline,rnd.nextLong());

            // simulate cpus
            Set<UniformCPU> cpus = new HashSet<UniformCPU>();

            for (int i=0; i < CPUNUM; i++) {
               double performanceIndex = rnd.nextInt(MAXCPUPERFORMANCE-MINCPUPERFORMANCE+1) + MINCPUPERFORMANCE;
               cpus.add(new UniformCPU(i,performanceIndex));
            }

//            cpus.add(new UniformCPU(0,1.0)); cpus.add(new UniformCPU(1,1.0));
            double totalCPUPerformanceIndex = getTotalCPUPerformanceIndex(cpus);

            Bug simulator = new Bug(clock,cpus,jobArrivalEventGenerator);
            boolean loop = false;
            for (String arg : args) {
               if (arg.equals("-ac")) {
                  System.out.println("Turn on admission control");
                  simulator.setAdmissionControl(true);   
               } else if (arg.equals("-np")) {
                  System.out.println("Use non preemptive backfilling scheduler");
                  simulator.setNonPreemptive(true);   
               } else if (arg.equals("-loop")) {
                  loop = true;
               } else {
                  System.out.println("Unknown option " + arg);
                  System.exit(1);
               }

            } 

            simulator.run();
            
            if (!loop) System.exit(0);
         }  // end for runIdx
      } // end for loadIdx

   }
}
